#ifndef HEAPSORT_H
#define HEAPSORT_H


namespace ED
{
template<typename T>
class HeapSort
{
    private  void heapify(int *vet, int pai, int heapsize)
    {
        int fl, fr, imaior;
        while (true)
        {
            fl = (pai << 1) + 1;
            fr = fl + 1;
            if ((fl < heapsize) && (vet[fl] > vet[pai])) imaior = fl;
            else imaior = pai;
            if ((fr < heapsize) && (vet[fr] > vet[imaior])) imaior = fr;
            if (imaior != pai)
            {
                troca(vet[pai], vet[imaior]);
                pai = imaior;
            }
            else break;
        }
    }
};

private void build_heap(int *vet, int n)
{
    for (i=(n>>1)-1; i>=0; i--)
        heapify(vet, i, n);
}

void heapsort(int *vet, int n)
{
    build_heap(vet, n);
    for (i=n-1; i > 0; i--)
    {
        troca(vet[0], vet[i]);
        heapify(vet, 0, i);
    }
}


}
#endif // HEAPSORT_H
